/* UNIVERSIDADE FEDERAL DE CAMPINA GRANDE - UFCG
 * Disciplina: Laboratorio de Estrutura de Dados
 * Professor: Marco Aurelio Spohn
 * Alunos: Alexandre Sales Vasconcelos       Mat.: 20621146
 * Atividade 6
 */

/**
 * Classe que implementa fila para o huffman.
 *
 * @version 1.0 2008/05/30
 * @author Alexandre Sales Vasconcelos
 * @see <a href="http://lab.eda.ufcg.googlepages.com/huffman"> Atividade 6 Problema 2</a>
 */
public class RowPriority {
	
	int[] alfabeto = new int[26];
	private NodeH nodeMinor;
	private int size;
	
	/**
	 * Construtor da classe RowPriority que cria uma fila para o huffman
	 * 
	 * @param string a ser codificada.
	 */
	public RowPriority(String string) {
		this.size = 0;
		this.nodeMinor = null;
		char caractere;
		string = string.toUpperCase();
		for (int i=0; i<string.length(); i++) {
			caractere = string.charAt(i);				
			if (caractere != '-') {
				insert(new NodeH(Character.toString(caractere),count(caractere,string)));
				string = string.replace(caractere, '-');
			}
		}
	}
	
	/**
	 * Metodo que conta quanto caracteres tem na string
	 * 
	 * @param c caractere a ser contado
	 * @param s string a ser verificada
	 * @return valor de repeticoes do caractere na string
	 */
	public static int count(char c, String s) {
		int retorno = 0;
		for (int i = 0 ; i < s.length() ; i++){
			if (s.charAt(i) == c) {
				retorno++;
			}
		}
		return retorno;
	}
	
	/**
	 * Metodo que insere na fila de huffman
	 * 
	 * @param nodo a ser inserido na fila
	 */
	public void insert(NodeH nodo) {
		
		if (size == 0) { // I
			this.nodeMinor = nodo;
			size++;
		}
		else {
			NodeH node = this.nodeMinor;
			NodeH nodeAux = null;
			boolean adicionou = false;
			while (node != null && adicionou == false) {
				nodeAux = node;
				if ((nodo.getFrequency() == node.getFrequency() && !nodo.character.equals("") && !node.character.equals("") && nodo.character.compareTo(node.character) < 0) || nodo.getFrequency()<node.getFrequency()) {  // II
					nodo.setNext(node);
					if (node.getPrevious() != null) {  // III
						node.getPrevious().setNext(nodo);
						nodo.setPrevious(node.getPrevious());
					}
					node.setPrevious(nodo);
					adicionou = true;
					if (node == this.nodeMinor) // IV
						this.nodeMinor = nodo;
				}
				else  // VI
					node = node.getNext();

			}
			if (node == null) {  // V
				nodeAux.setNext(nodo);
				nodo.setPrevious(nodeAux);
			}
			size++;
		}
	}
	
	/**
	 * Metodo que extrai e retorna o no com menor frequencia
	 * 
	 * @return no de menor frequenca
	 */
	public NodeH extractMin() {
		NodeH next = this.nodeMinor.getNext();
		NodeH minor = this.nodeMinor;
		if (next != null) {
			next.setPrevious(null);
			this.nodeMinor.setNext(null);
		}	
		this.nodeMinor = next;
		size--;
		return minor;
	}
	
	/**
	 * Metodo que retorna o numero de elementos da fila
	 * 
	 * @return numero de elementos
	 */
	public int getSize() {
		return size;
	}	

	/**
	 * Metodo que retorna o primeiro no da fila.
	 * 
	 * @return primero no da fila
	 */
	public NodeH getMenor() {
		return this.nodeMinor;
	}
}
